package org.example;

import java.util.*;

public class Test1 {
    //leetcode 最小高度树
    //https://leetcode.cn/problems/minimum-height-trees/description/?envType=problem-list-v2&envId=depth-first-search
    /**
     通过观察可以发现，要求的的节点总是树种两个节点的最长距离的中间节点，所以我们可以像剥洋葱一样的
     一层一层的拨开叶子节点
     */
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ret = new ArrayList<>();
        if (n == 1) {
            ret.add(0);
            return ret;
        }
        int[] degrees = new int[n]; //记录各个节点的度
        Map<Integer,List<Integer>> map = new HashMap<>(); //记录各个节点的邻居节点
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];

            degrees[a]++;
            degrees[b]++;

            if (map.get(a) == null) {
                map.put(a,new ArrayList<>());
            }
            if (map.get(b) == null) {
                map.put(b,new ArrayList<>());
            }
            map.get(a).add(b);
            map.get(b).add(a);
        }
        LinkedList<Integer> leafNodes = new LinkedList<>(); //先遍历一遍degree，统计一下叶子结点
        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i] == 1) {
                leafNodes.add(i);
            }
        }

        while (leafNodes.size() > 0) {
            //清除ret，这样可以保证ret最终存储的是最内层的节点
            ret.clear();
            //像剥洋葱一样，一步一步将度为1的也就是叶子节点剥离出去
            int size = leafNodes.size();
            for (int i = 0; i < size; i++) {
                int leaf = leafNodes.poll();
                ret.add(leaf);
                List<Integer> neighbors = map.get(leaf);
                //将叶子节点剥离出去之后，与之对应的节点的度就减少了1
                for (int neighbor : neighbors) {
                    degrees[neighbor]--;
                    //判断剥离出去一层叶子节点之后，新生成的叶子节点
                    if (degrees[neighbor] == 1) {
                        leafNodes.add(neighbor);
                    }
                }
            }
        }
        return ret;
    }
}
